package com.leetcode.剑指Offer;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 * 
 * @author LZF
 *	步骤：判断A是否包含B，如果不包含，则继续判断A的左或A的右是否包含B
 */	
public class Offer26树的子结构 {
	/**
	 * 
	 * @param A 
	 * @param B
	 * @return A是否包含B
	 */
	public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B == null) return false;
        return dfs(A,B);
    }
	/**
	 * 
	 * @param A
	 * @param B
	 * @returns 返回以A作为根节点，是否包含B
	 */
    public boolean AcontainB(TreeNode A, TreeNode B){
        if(B == null) return true;
        if(A == null) return false;
        if(A.val != B.val) return false;
        return AcontainB(A.left,B.left) && AcontainB(A.right,B.right);
    }
    /**
     * 
     * @param A
     * @param B
     * @return A是否包含B
     */
    public boolean dfs(TreeNode A, TreeNode B){
        if(A == null) return false;
        //如果当前A作为根节点不B，那就继续判断A的左子树或A的右子树是否包含B
        if(!AcontainB(A,B)) return dfs(A.left,B) || dfs(A.right,B);
        return true;
    }
    //树的定义
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}
